package com.cet.algorithm.二叉树.路径总和;

import java.util.ArrayList;
import java.util.List;

/**
 * @program: algorithm
 * @description: 路径总和2
 * @author: 陈恩涛
 * @create: 2022-07-25 14:35
 **/
public class LC113 {

    public static void main(String[] args) {
        final TreeNode root = new TreeNode(5, new TreeNode(4, new TreeNode(11, new TreeNode(7), new TreeNode(2)), null), new TreeNode(8, new TreeNode(13), new TreeNode(4, new TreeNode(5), new TreeNode(1))));
        final List<List<Integer>> lists = new LC113().pathSum(root, 22);
        for (List<Integer> list : lists) {
            list.forEach(System.out::print);
            System.out.print("\n");
        }
    }

    /**
     * 递归
     * @param root
     * @param targetSum
     * @return
     */
    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        final List<List<Integer>> result = new ArrayList<>();
        if (root == null) {
            return result;
        }
        List<Integer> paths = new ArrayList<>();
        traversal(root, paths, result, targetSum);
        return result;
    }

    private void traversal(TreeNode node, List<Integer> paths, List<List<Integer>> result, int targetSum) {
        paths.add(node.val);
        if (node.left == null && node.right == null && paths.stream().reduce(Math::addExact).get() == targetSum) {
            final List<Integer> temp = new ArrayList<>(paths);
            result.add(temp);
            return;
        }
        if (node.left != null) {
            traversal(node.left, paths, result, targetSum);
            paths.remove(paths.size() - 1);
        }
        if (node.right != null) {
            traversal(node.right, paths, result, targetSum);
            paths.remove(paths.size() - 1);
        }
    }
}
